package flashBack;

/**
 * @author zxc
 * @date 2023/01/17 10:28
 **/

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 * 题目 ：包含重复元素的全排列
 * 题目详述 ：
 * 给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。
 */
public class PermuteUnique {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        flushBack(nums , 0 , result);
        return result;
    }
    private void flushBack(int[] nums, int index, List<List<Integer>> result) {
        if(index == nums.length){
            List<Integer> num = new LinkedList<>();
            // 由于我们是通过对于nums数组中元素进行位置交换操作，来实现获取当前数组所有可能的全排列
            // 即，当index == nums.length时，我们需要将当时nums中元素顺序地存储到num集合;
            for (int i : nums) {
                num.add(i);
            }
            result.add(num);
        }
        else if(index < nums.length){
            // 即，使用set集合，来存储 已经和下标index所对应的数组元素交换过的所有值
            HashSet<Integer> set = new HashSet<>();
            for(int i = index ; i < nums.length ; i++){
                // 区别 ：即，有且仅有在set集合中不包含nums[i],也就是代表了nums[i]该元素并未与 下标index所对应的元素交换过;
                if(!set.contains(nums[i])){
                    // 若是当前遍历的nums[i]元素之前并未与 下标index所对应的元素交换过，由于后续会去进行swap操作，
                    // 所以可以将当前nums[i]元素加入到set集合中，来代表该nums[i]元素也已经和 下标index所对应的数组元素交换过;
                    set.add(nums[i]);
                    swap(nums , index , i);
                    flushBack(nums , index + 1 , result);
                    swap(nums , index , i);
                }
            }
        }

    }
    // 传入nums数组，将nums数组中index和i下标所对应的数组元素进行交换
    private void swap(int[] nums , int index, int i) {
        if(index != i){
            int temp = nums[index];
            nums[index] = nums[i];
            nums[i] = temp;
        }
    }
}
